Definition

For i≥1i \geq 1, language LL is in 𝚺ip\mathbf{\Sigma}_i^p if there exists a polynomial time TM MM and polynomial qq such that

x \in L \iff \exists u_{1} \in \{0,1\}^{q(|x|)} \forall u_2 \in \{0,1\}^{q(|x|)}... Q_i u_i \in \{0,1\}^{q(|x|)} M(x,u_1,...,u_i)=1$$ where $Q_i$ denotes ([[quantifier]]) $\forall$ or $\exists$ depending on whether $i$ is even or odd, respectively. Then the **polynomial hierarchy** is the set $\mathbf{PH} = \cup_i \mathbf{\Sigma}_i^p$. ## See also - [[Fagin's theorem]] - [[class PSPACE|PSPACE]] - [[existential second-order logic|ESO]] - [[class P|P]] - [[class NP|NP]] - [[P versus NP problem]] --- ## References 1. https://en.wikipedia.org/wiki/Polynomial_hierarchy 2. S. Arora, B. Barak. _Computational Complexity: A Modern Approach_, Cambridge University Press, 2009, pp. 95-104. 3. https://www.cl.cam.ac.uk/teaching/0910/L15/handout5.pdf ParseError: Can't use function '$' in math mode at position 132: …,u_1,...,u_i)=1$̲$ where $Q_i$ d…